<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>binary_search</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>binary_search</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>

<h3>Prototype</h3>
<tt>Binary_search</tt> is an overloaded name; there are actually two <tt>binary_search</tt>
functions.
<pre>
template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class <A href="LessThanComparable.html">LessThanComparable</A>&gt;
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const LessThanComparable&amp; value);

template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class T, class <A href="StrictWeakOrdering.html">StrictWeakOrdering</A>&gt;
bool binary_search(ForwardIterator first, ForwardIterator last, const T&amp; value,
                   StrictWeakOrdering comp);
</pre>                   
<h3>Description</h3>
<tt>Binary_search</tt> is a version of binary search: it attempts to find the
element <tt>value</tt> in an ordered range <tt>[first, last)</tt>  It returns 
<tt>true</tt> if an element that is equivalent to <A href="#1">[1]</A> <tt>value</tt> is present in
<tt>[first, last)</tt> and <tt>false</tt> if no such element exists.  <A href="#2">[2]</A>
The first version of <tt>binary_search</tt>
uses <tt>operator&lt;</tt> for comparison, and the second uses the 
<A href="functors.html">function object</A> <tt>comp</tt>.
<P>
Specifically, the first version returns <tt>true</tt> if
and only if there exists an iterator <tt>i</tt> in <tt>[first, last)</tt> such that
<tt>*i &lt; value</tt> and <tt>value &lt; *i</tt> are both <tt>false</tt>.  
The second version returns <tt>true</tt> if
and only if there exists an iterator <tt>i</tt> in <tt>[first, last)</tt> such that
<tt>comp(*i, value)</tt> and <tt>comp(value, *i)</tt> are both <tt>false</tt>.  
<h3>Definition</h3>
Defined in the standard header <A href="algorithm">algorithm</A>, and in the nonstandard
backward-compatibility header <A href="algo.h">algo.h</A>.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>LessThanComparable</tt> is a model of <A href="LessThanComparable.html">LessThan Comparable</A>.
<LI>
The ordering on objects of type <tt>LessThanComparable</tt> is a <i>strict
   weak ordering</i>, as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements.
<LI>
<tt>ForwardIterator</tt>'s value type is the same type as <tt>LessThanComparable</tt>.
</UL>
For the second version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>StrictWeakOrdering</tt> is a model of <A href="StrictWeakOrdering.html">Strict Weak Ordering</A>.
<LI>
<tt>ForwardIterator</tt>'s value type is the same type as <tt>T</tt>.
<LI>
<tt>ForwardIterator</tt>'s value type is convertible to <tt>StrictWeakOrdering</tt>'s
   argument type.
</UL>
<h3>Preconditions</h3>
For the first version:
<UL>
<LI>
<tt>[first, last)</tt> is a valid range.
<LI>
<tt>[first, last)</tt> is ordered in ascending order according to
   <tt>operator&lt;</tt>.  That is, for every pair of iterators <tt>i</tt> and <tt>j</tt>
   in <tt>[first, last)</tt> such that <tt>i</tt> precedes <tt>j</tt>, 
   <tt>*j &lt; *i</tt> is <tt>false</tt>.
</UL>
For the second version:
<UL>
<LI>
<tt>[first, last)</tt> is a valid range.
<LI>
<tt>[first, last)</tt> is ordered in ascending order according to
   the <A href="functors.html">function object</A> <tt>comp</tt>.  That is, for every pair of iterators <tt>i</tt> and <tt>j</tt>
   in <tt>[first, last)</tt> such that <tt>i</tt> precedes <tt>j</tt>, 
   <tt>comp(*j, *i)</tt> is <tt>false</tt>.
</UL>
<h3>Complexity</h3>
The number of comparisons is logarithmic: at most <tt>log(last - first) +
2</tt>.  If <tt>ForwardIterator</tt> is a <A href="RandomAccessIterator.html">Random Access Iterator</A> then the
number of steps through the range is also logarithmic; otherwise, 
the number of steps is proportional to <tt>last - first</tt>.  <A href="#3">[3]</A>
<h3>Example</h3>
<pre>
int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i &lt;= 10; ++i) {
    cout &lt;&lt; &quot;Searching for &quot; &lt;&lt; i &lt;&lt; &quot;: &quot;
         &lt;&lt; (binary_search(A, A + N, i) ? &quot;present&quot; : &quot;not present&quot;) &lt;&lt; endl;
  }
}
</pre>
The output is:
<pre>
Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that you may use an ordering that is a strict weak ordering
but not a total ordering; that is, there might be values <tt>x</tt> and <tt>y</tt>
such that <tt>x &lt; y</tt>, <tt>x &gt; y</tt>, and <tt>x == y</tt> are all <tt>false</tt>.  (See the
<A href="LessThanComparable.html">LessThan Comparable</A> requirements for a more complete discussion.)
Finding <tt>value</tt> in the range <tt>[first, last)</tt>, then, doesn't mean
finding an element that is equal to <tt>value</tt> but rather one that is
<i>equivalent to</i> <tt>value</tt>: one that is neither greater than nor less
than <tt>value</tt>.  If you're using a total ordering, however (if you're
using <tt>strcmp</tt>, for example, or if you're using ordinary arithmetic
comparison on integers), then you can ignore this technical
distinction: for a total ordering, equality and equivalence are
the same.
<P><A name="2">[2]</A>
Note that this is not necessarily the information you are
interested in!  Usually, if you're testing whether an element is
present in a range, you'd like to know where it is (if it's present), 
or where it should be inserted (if it's not present).  The functions
<tt><A href="lower_bound.html">lower_bound</A></tt>, <tt><A href="upper_bound.html">upper_bound</A></tt>, and <tt><A href="equal_range.html">equal_range</A></tt> provide
this information.
<P><A name="3">[3]</A>
This difference between <A href="RandomAccessIterator.html">Random Access Iterators</A> and
<A href="ForwardIterator.html">Forward Iterators</A> is simply because <tt><A href="advance.html">advance</A></tt> is constant
time for <A href="RandomAccessIterator.html">Random Access Iterators</A> and linear time for 
<A href="ForwardIterator.html">Forward Iterators</A>.
<h3>See also</h3>
<tt><A href="lower_bound.html">lower_bound</A></tt>, <tt><A href="upper_bound.html">upper_bound</A></tt>, <tt><A href="equal_range.html">equal_range</A></tt>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
